package com.leetcode.根据数据结构分类.队列;


import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: xiaomi
 * @date: 2021/2/15
 * @description: 146. LRU 缓存机制
 * https://leetcode-cn.com/problems/lru-cache/
 * 居然可以使用 LinkedHashMap 来实现！
 */
public class B_146_LRU缓存机制 {

    public static void main(String[] args) {
        test1();
        test2();
        test3();
        test4();
    }

    public static void test1() {
        LRUCache2 cache = new LRUCache2(1);
        cache.put(2, 1);
        System.out.println(cache.get(2));
        cache.put(3, 2);
        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
    }

    public static void test2() {
        LRUCache2 cache = new LRUCache2(3);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.put(4, 4);
        System.out.println(cache.get(4));
        System.out.println(cache.get(3));
        System.out.println(cache.get(2));
        System.out.println(cache.get(1));
        cache.put(5, 5);
        System.out.println(cache.get(1));
        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
        System.out.println(cache.get(5));
    }

    public static void test3() {
        LRUCache2 cache = new LRUCache2(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }

    public static void test4() {
        LRUCache2 cache = new LRUCache2(2);
        cache.put(2, 1);
        cache.put(2, 2);
        System.out.println(cache.get(2));
        cache.put(1, 1);
        cache.put(4, 1);
        System.out.println(cache.get(2));
    }


    /**
     * LinkedList 是可以实现的，但是查找是 O(n) ;
     * HashMap 实现的话，不也是需要 O(n) 的维护吗
     * --
     * 这种方式会超过时间限制了
     */
    static class LRUCache {


        int cap = 0;
        /**
         * 存储 key
         */
        List<Integer> deque = new LinkedList<>();
        HashMap<Integer, Integer> map;


        public LRUCache(int capacity) {
            map = new HashMap<>(capacity);
            cap = capacity;
        }

        public int get(int key) {
            Integer res = map.get(key);
            for (int i = 0; i < deque.size(); i++) {
                if (deque.get(i) == key) {
                    deque.remove(i);
                    deque.add(0, key);
                    break;
                }
            }
            return res == null ? -1 : res;
        }

        public void put(int key, int value) {
            Integer val = map.get(key);
            if (val == null) {
                if (deque.size() == cap) {
                    //需要删除元素
                    Integer remove = deque.remove(cap - 1);
                    map.remove(remove);
                }
                deque.add(0, key);

            } else {
                for (int i = 0; i < deque.size(); i++) {
                    if (deque.get(i) == key) {
                        deque.remove(i);
                        deque.add(0, key);
                        break;
                    }
                }
            }

            map.put(key, value);
        }
    }

    /**
     * 依然是通过 HashMap + LinkedList 的方式，但是后者是自己定义的
     */
    static class LRUCache2 {

        /**
         * key - Node(value , Node)
         */
        HashMap<Integer, Node> map = new HashMap<>();
        /**
         * 哨兵节点（prev 指向 tail ; next 指向 head）
         */
        Node guard = new Node(0, 0, null, null);
        /**
         * 头节点
         */
        Node head = new Node(0, 0, null, null);
        /**
         * 尾节点
         */
        Node tail = new Node(0, 0, null, null);

        /**
         * 容量
         */
        int capacity;

        /**
         * 实际大小
         */
        int size;

        public LRUCache2(int capacity) {
            this.capacity = capacity;
        }

        /**
         * @param key
         * @return
         */
        public int get(int key) {
            Node node = map.get(key);
            if (node == null) {
                return -1;
            }
            //此时 map 中存在对于的 key
            if (head.equals(node)) {
                //如果已经是头节点了
                return node.value;
            }


            //不是头节点，需要调整
            //1.remove node
            node.prev.next = node.next;
            if (node.next != null) {
                //说明 node 不是 tail
                node.next.prev = node.prev;
            }else {
                tail = node.prev;
            }


            //2.insert head
            node.prev = guard;
            guard.next = node;
            node.next = head;
            head.prev= node;
            head = node;
            return node.value;
        }

        public void put(int key, int value) {
            Node node = map.get(key);
            if (node != null) {
                //如果 key 已经存在 -> 更新值，并且将 链表进行更新
                node.value = value;

                //同上
                //此时 map 中存在对于的 key
                if (head.equals(node)) {
                    //如果已经是头节点了
                    return ;
                }


                //不是头节点，需要调整
                //1.remove tail node
                node.prev.next = node.next;
                if (node.next != null) {
                    //说明 node 不是 tail
                    node.next.prev = node.prev;
                }else {
                    tail = node.prev;
                }


                //2.insert head
                node.prev = guard;
                guard.next = node;
                node.next = head;
                head.prev= node;
                head = node;

                return;
            }
            //此时是新增
            node = new Node(key, value, null, null);
            map.put(key, node);
            if (size == capacity) {
                //如果已经满了
                map.remove(tail.key);

                //删除尾元素
                tail.prev.next = null;
                tail = tail.prev;

                //新增 头
                //2.insert head
                node.prev = guard;
                guard.next = node;
                node.next = head;
                head.prev= node;
                head = node;
            } else {
                //2.insert head
                node.prev = guard;
                guard.next = node;
                if (size == 0){
                    head = node;
                    tail = head;
                }else {
                    node.next = head;
                    head.prev= node;
                    head = node;
                }

                size++;
            }

        }


    }

    /**
     * 为了方便删除，新增 prev 节点
     */
    static class Node {
        public int key;
        public int value;
        /**
         * 前节点
         */
        public Node prev;
        /**
         * 后节点
         */
        public Node next;

        public Node(int key, int value, Node prev, Node next) {
            this.key = key;
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }

}
